package Basic;
//统计n以内的素数个数(除1和n本身，没有可以整除的)
public class CountPrime {
    public static void main(String[] args) {
        System.out.println(eratosthenes(100));

    }


    //    埃筛法
    public static int eratosthenes(int n) {
        boolean[] isPrime = new boolean[n]; //false代表素数  初始值全为false
        int count=0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]){
                count++;
                for (int j = i * i; j < n; j += i) {  //先排除一部分合数   //(int j = 2 * i;)  剪枝:从i开始 i*i i*(i+1) i*(i+2)
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }


//    暴力法
    public static int bf(int num) {

        int ans=1;  //2是素数
        boolean flag;

        for (int i = 3; i <= num; i++) {
            flag=true;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    flag=false;
                    break;
                }
            }
            if (flag == true) {
                ans++;
            }
        }
        return ans;
    }

}